POI2008 Blockade

POI
图的连通性, 块割树

POI2008 Blockade

题目大意：

城市中有n个小镇，m条双向边。每一条双向边连接两个不同的小镇，保证没有重复的边，并且保证所有的小镇连通。输出n个数，代表如果把第i个点删掉，将有多少个点对不能互通。

($ n \le 10^5 $ , $ m \le 5 \times 10^5 $ )

题解：

首先来介绍一下块割树（并不知道明确的定义，仅凭理解扯皮）：

我们知道一个无向图的割点可能属于多个点双连通分量，因而一般我们进行点双连通分量分解时在栈中存边，以每一条边的归属来把图分解。

但块割树并不在栈中存边，它在栈中存点。那如何解决一个割点属于多个点双连通分量的情况呢?

块割树在缩点时，并不把一个点双连通分量看做一个节点。每一个点双连通分量除去割点的部分缩为一个点，割点独自成点。这样就能够保证把图缩为一棵树。并且不会存在一个点在缩点后属于多个节点的情况。

接下来看看这道题：

首先我们点双联通分量分解，构造出一棵块割树。

若去掉的点不是割点，那么答案即为$(n-1) \times 2$.

否则，要加上由于割点去掉而使得一些点对不再相连的情况。这个树形dp搞一下就可以了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=100001,M=500001;
int n,m,tot_edge,head[N<<1];
struct Edge{
	int to,nxt;
}edge[M<<1];
void add_edge(int a,int b){
	edge[tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge++;
}
int tot,low[N],dfn[N],stk[N],top;
vector<vec>blo;
vec cut;
void pack(int p,int to){
	vec tmp=vec(1,p);
	for(;;){
		int cur=stk[top];top--;
		tmp.push_back(cur);
		if(cur==to)break;
	}
	blo.push_back(tmp);
}
void Tarjan(int p){
	low[p]=dfn[p]=++tot;
	stk[++top]=p;
	bool ok=false;
	int child=0;
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(!dfn[to]){
			Tarjan(to);child++;
			low[p]=min(low[p],low[to]);
			if(low[to]>=dfn[p]){
				ok=true;
				pack(p,to);
			}
		}else low[p]=min(low[p],dfn[to]);
	}
	if(dfn[p]==1){
		ok=child>1;
		if(!child)blo.push_back(vec(1,p));
	}
	if(ok)cut.push_back(p);
}
int idx[N],cnt[N<<1],num[N<<1],fa[N<<1];
void dfs(int p,int f){
	cnt[p]=num[p],fa[p]=f;
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		dfs(to,p);
		cnt[p]+=cnt[to];
	}
}
ll ans[N];
int solve(){
	for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
	return 0;
}
int main(){
	Rd(n),Rd(m);
	memset(head,-1,sizeof(head));
	for(int i=1,a,b;i<=m;i++){
		Rd(a),Rd(b);
		add_edge(a,b);
		add_edge(b,a);
	}
	Tarjan(1);
	for(int i=0;i<cut.size();i++){
		int p=cut[i];
		idx[p]=blo.size()+i+1;
	}
	memset(head,-1,sizeof(head)),tot_edge=0;
	for(int i=0;i<blo.size();i++){
		const vec& cur=blo[i];
		vec tmp;
		for(int j=0;j<cur.size();j++){
			int p=cur[j];
			if(idx[p]){
				add_edge(i+1,idx[p]);
				add_edge(idx[p],i+1);
			}else num[i+1]++;
		}
	}
	for(int i=0;i<cut.size();i++)num[idx[cut[i]]]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++)ans[i]=n-1<<1;
	for(int i=0;i<cut.size();i++){
		int p=cut[i],id=idx[p];
		for(int j=head[id];~j;j=edge[j].nxt){
			int to=edge[j].to;
			if(to==fa[id])continue;
			ans[p]+=1LL*cnt[to]*(n-1-cnt[to]);
		}
		int c=n-cnt[id];
		ans[p]+=1LL*c*(n-1-c);
	}
	return solve();
}
分享到 评论